1. Field of the Invention
The present invention relates to an image processing method, image processing apparatus, and program and, more particularly, to a core line modification method of a thinning figure in an image process.
2. Description of the Related Art
A thinning process is a process for converting an input binary image so that each figure pixel has a 1-pixel width. According to the thinning process, unlike a shrinkage process which simply deletes figure pixels (black pixels) that contact background pixels (white pixels), a core line that represents the center line of a line part of a figure can be extracted while holding the topology (positional relation/connection relation) of the figure. The thinning processing is an image process method which is popularly used as a pre-process of character recognition, pattern recognition, and vectorization. The thinning process has been studied through the ages, and various methods have been proposed. Of these methods, a Hilditch thinning method is prevalent as a known thinning method (for example, see Agui & Nagao, “Fundamentals of C-based image processing”, first edition, ISBN4-7856-3124-4, Shokodo, published on Nov. 20, 2000, pp. 53-58).
In the Hilditch thinning method, using a 3×3 window, which refers to a pixel of interest and eight pixels around the pixel of interest, as a basic process unit, the entire image data is raster-scanned to process each pixel as a pixel of interest, thus attaining a thinning process. When a certain pixel is selected as a pixel of interest, it is determined if that pixel meets thinning deletion conditions which are defined in advance for each 3×3 window. If the pixel of interest meets the deletion conditions, a process for deleting the pixel of interest, that is, replacing a figure pixel by a background pixel is executed. On the other hand, if the pixel of interest does not meet the deletion conditions, the next pixel in the raster scan order is selected as a pixel of interest, and the same process is executed for a new 3×3 window. This process is repeated for all pixels of the image data. Then, a series of processes in the raster scan are repeated until all pixels to be deleted are removed in a single raster scan. When all pixels to be deleted are removed in the single raster scan, the thinning process is completed. FIG. 3 shows an example of the process result of the Hilditch thinning method. 3a in FIG. 3 shows an original image, and 3b in FIG. 3 shows the result of the thinning process based on the Hilditch thinning method. 3c in FIG. 3 is a view showing an image obtained by overlapping the original image and the thinning processed image. As can be seen from 3c in FIG. 3, the thinning processed image becomes nearly a core line image of the original image.
In the thinning process, since the topology of a figure of the original image has to be held, the deletion conditions have to include a constraint “when a line width to be processed reaches one pixel, no more deletion is made”. However, in the Hilditch thinning method, whether or not to delete a certain pixel of interest is determined with reference to only eight neighboring pixels around the pixel of interest. For example, since a 3×3 window (i) in 3c in FIG. 3 includes pixels of a corner portion of a broken line, it is desired to delete the pixel of interest in the 3×3 window (i) so as to express the broken line by a single core line without any branch. On the other hand, since a 3×3 window (ii) includes pixels of an end portion of a line image, it is desired not to delete the pixel of interest since the length of a line of the original image is different from that of a line of the core line if that pixel is deleted. However, in only a layout of pixels in a 3×3 window, since only eight neighboring pixels around the pixel of interest are referred to, whether or not to delete the pixel of interest cannot be adaptively determined. For this reason, if the thinning conditions are set not to delete a central pixel (pixel of interest) of the window (ii), a pixel to be deleted unwantedly remains at the edge of a straight line or a corner like in the window (i). Hence, a thinning method which determines whether or not to delete a pixel with reference to a range broader than eight neighboring pixels around a pixel of interest has been proposed. However, a thinning method which can practically be free from any remaining pixels to be deleted has never been proposed. The remaining pixels to be deleted are also called a branch line noise, and a core line has to be used after this branch line noise of the thinning result is removed.
FIG. 4 shows an example obtained when a thinning process based on the pixel layout in a 3×3 window is applied to an image including solid regions (plane portions), shown in 4a in FIG. 4, as in FIG. 3. When the thinning process is applied to an image including solid regions, an image obtained by deleting each plane to be an oblique line is obtained as the process result. The oblique line observed in the thinning result of the plane portion is not a branch line noise as a result of thinning but it can be considered as a core line that expresses the feature of a plane region. Hence, in order to use the oblique line obtained by processing the plane as a core line that expresses a plane portion in a post-process, this oblique line is a core line component which is not to be removed as a branch line noise.
In 4b in FIG. 4, when the core line of the thinning result is separated for respective intersections, in an interval ab (an interval from an intersection a to an intersection b via an upper left corner of 4c in FIG. 4) which connects the intersections a and b in 4c in FIG. 4, a core line which expresses a monospaced line (a core line generated by applying a thinning process to a portion of a line having a constant line width) and a core line which expresses the plane (a core line generated by applying a thinning process to the plane portion) are unwantedly mixed. That is, in the post-process after thinning, even when the core line of the monospaced line portion and that of a non-monospaced line portion (plane portion) have to be separately handled, if the type of each line is determined for each unit divided based on intersections, the plane and a monospaced line cannot be appropriately separated.
On the other hand, as a method of removing each branch line noise from a thinning image, a method of detecting the branch point and end point of a core line, and extracting and deleting figure pixels which include the end point and have a length equal to or smaller than a predetermined value is available (for example, see Japanese Patent Laid-Open No. 5-94525). With this technique, a branch line noise having a predetermined length or less can be deleted from the thinning image.
Also, a technique called distance transformation is known. The distance transformation is a process for replacing values of figure pixels in a binary image by distance values from background pixels. By executing the distance transformation, a distance from each figure pixel to the nearest background pixel can be calculated. (For example, see Junichiro Toriwaki, “Digital image processing for image understanding (II)”, first edition, ISBN4-7856-2004-8, Shokodo, published on Apr. 30, 1988, pp. 32-37, etc.)